package edu.dayu.demo1;


/**
 * 输入：nums = [1,4,2,7], low = 2, high = 6
 * 输出：6
 * 解释：所有漂亮数对 (i, j) 列出如下：
 *     - (0, 1): nums[0] XOR nums[1] = 5
 *     - (0, 2): nums[0] XOR nums[2] = 3
 *     - (0, 3): nums[0] XOR nums[3] = 6
 *     - (1, 2): nums[1] XOR nums[2] = 6
 *     - (1, 3): nums[1] XOR nums[3] = 3
 *     - (2, 3): nums[2] XOR nums[3] = 5
 *  意思就是 数组的两个数 异或的结果 在给定的范围内 就是符合题意
 *  思路1： 最初思路就是 用一个双重循环，然后 从数组下标 0 开始，到 倒数第二个数 时间复杂度 O（n^2），但是感觉会超时。
 *  官方思路：通过字典树来解决（未理解） 字典树就是父节点中的数据是子节点数据的前缀  比如父节点 1 子节点 10、11..
 *          官方是计算 异或结果 小于high - 小于low的 就是这个范围的了。 通过字典树来计算 数组中异或结果小于 high 的个数（怎么计算）
 */
public class 统计异或值在范围内的数对有多少 {
    public static void main(String[] args) {
        int[] nums = {3856,3174,2182,7497,6155,4589,3581,4548,3982,2508};
        System.out.println(countPairs(nums, 6903, 6946));
    }

    public static int countPairs(int[] nums, int low, int high){
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j =i+1;j<nums.length;j++){
                int temp = nums[i]^nums[j];
                if (temp>=low&&temp<=high)
                    sum++;
            }
        }
        return sum;
    }

    /**
     * 快排
     * @param nums
     * @param i
     * @param j
     */
    public static void sort(int[] nums,int i,int j){
        if (i>=j){
            return;
        }
        int val = nums[i];
        int l = i;
        int r = j;
        while (l<r){
            // 从后往前找第一个小于 val 的数
            while (l<r && nums[r] > val){
                r--;
            }
            if (l < r){
                nums[l++] = nums[r];
            }
            //从前往后找第一个大于val的数字
            while (l < r && nums[l] < val){
                l ++;
            }
            if(l < r){//找到了数字
                nums[r--] = nums[l];
            }
        }
        nums[l] = val;
        sort(nums,i,l-1);
        sort(nums,l+1,j);
    }

}
